#include <vector>
#include <stack>

using namespace std;


class Solution {
public:
    // 方法一：左遍历 + 右遍历 动态规划
    // O(n), O(n)
    int trap(vector<int>& height) {
        if (!height.size()) return 0;  // edge case: []
        int n = height.size();
        vector<int> leftMax(n);
        vector<int> rightMax(n);

        // 从左往右遍历
        leftMax[0] = height[0];
        for (int i=1; i<n; ++i) {
            leftMax[i] = max(height[i], leftMax[i-1]);
        }

        // 从右往左遍历
        rightMax[n-1] = height[n-1];
        for (int i=n-2; i>=0; --i) {
            rightMax[i] = max(height[i], rightMax[i+1]);
        }

        int res = 0;
        for (int i=0; i<n; ++i) {
            res += min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }

    // 方法二：单调栈
    //* 单调栈里维护着单调递减的下标，关注三个位置：
    //*     top, top 的前一个 left, 当前遇到的 i
    //*     而且 height[left] >= height[i]
    //* 若 i 比 top 更高，则有雨水区域，需要出栈:
    //*     雨水宽度为 i - left - 1
    //*     雨水高度为 min(height[left], height[i]) - height[top]
    //* 不断往前出栈，记录更上层的雨水量。
    //* O(n), O(n)
    int trap(vector<int>& height) {
        int n = height.size();
        if (n <= 2) return 0;
        int res = 0;

        stack<int> stk; stk.push(0);
        for (int i=1; i<n; ++i) {
            while (!stk.empty() && height[stk.top()] < height[i]) {
                int top = stk.top(); stk.pop();
                if (stk.empty()) break;
                int left = stk.top();
                int h = min(height[left], height[i]) - height[top];
                res += (i-left-1) * h;
            }
            stk.push(i);
        }

        return res;
    }

    // 方法三：双指针
    // O(n), O(1)
};
